
/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <deque>
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
  RC   rc;
  char page[PageFile::PAGE_SIZE];

  // open the page file
  if ((rc = pf.open(indexname, mode)) < 0) return rc;
  
  //
  // in the rest of this function, we set the end record id
  //

  // get the end pid of the file
  // erid.pid = pf.endPid();

  // if the end pid is zero, the file is empty.
  if (pf.endPid() == 0) {
    // init new index.
    rootPid = -1;
    treeHeight = 0;
    numNodes = 0;
    writeMetadata();
    return 0;
  }

  // read metadata from first page.
  if ((rc = pf.read(0, page)) < 0) {
    // an error occurred during page read
    pf.close();
    return rc;
  }

  // get # records in the last page
  memcpy(&rootPid, &page, sizeof(int));
  memcpy(&treeHeight, &page[4], sizeof(int));
  memcpy(&numNodes, &page[8], sizeof(int));

  return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
  writeMetadata();
  return pf.close();
}

void BTreeIndex::writeMetadata(){
  char page[PageFile::PAGE_SIZE];
  memcpy(&page, &rootPid, sizeof(int));
  memcpy(&page[4], &treeHeight, sizeof(int));
  memcpy(&page[8], &numNodes, sizeof(int));
  pf.write(0,page);
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
  int rc;
  // root node case
  if (treeHeight == 0) {
    BTLeafNode leaf = BTLeafNode();
    rc = leaf.insert(key,rid);
    rootPid = pf.endPid();
    rc += leaf.write(rootPid,pf);
    treeHeight++;

  } else {
    PageId newPid;
    int newKey;
    rc = insertRec(key, rid, 1, rootPid, newPid, newKey);
  }
  
  return rc;
}
RC BTreeIndex::insertRec(int key, const RecordId& rid, int depth, PageId pid, PageId& newPid, int& newKey){
    int insertSuccess = 0;
    if (depth == treeHeight) {
      BTLeafNode leaf = BTLeafNode();
      leaf.read(pid,pf);
      insertSuccess = leaf.insert(key,rid);

      if (insertSuccess == 0) {
        leaf.write(pid,pf);
        return 0;
      } else {
        //split node
        BTLeafNode sibling = BTLeafNode();
        PageId siblingPid = pf.endPid();
        int siblingKey;

        insertSuccess = leaf.insertAndSplit(key, rid, sibling, siblingKey);

        leaf.setNextNodePtr(siblingPid);
        insertSuccess += leaf.write(pid, pf);
        
        sibling.write(siblingPid,pf);
        
        newKey = siblingKey;
        newPid = siblingPid;

        if(depth == 1){
          BTNonLeafNode newRoot = BTNonLeafNode();
          insertSuccess += newRoot.initializeRoot(pid, newKey, siblingPid);
          rootPid = pf.endPid();
          insertSuccess += newRoot.write(rootPid,pf);
          treeHeight++;
        }

        if (insertSuccess < 0)
          return -1;

        return 1;
      }
    } else {
      BTNonLeafNode node = BTNonLeafNode();
      node.read(pid, pf);

      int nextPid;
      if (node.locateChildPtr(key, nextPid) < 0) {
        return -1;
      }
      
      PageId bubblePid;
      int bubbleKey;
      insertSuccess = insertRec(key, rid, depth+1, nextPid, bubblePid, bubbleKey);

      if (insertSuccess == 1) {
        insertSuccess = node.insert(bubbleKey,bubblePid);

            if (insertSuccess < 0) {
              BTNonLeafNode sibling = BTNonLeafNode();
              PageId siblingPid = pf.endPid();
              int midKey;

              insertSuccess = node.insertAndSplit(bubbleKey, bubblePid, sibling, midKey);
              insertSuccess += node.write(pid, pf);
              sibling.write(siblingPid,pf);

              if(depth == 1){
                BTNonLeafNode newRoot = BTNonLeafNode();
                insertSuccess += newRoot.initializeRoot(pid, midKey, siblingPid);
                rootPid = pf.endPid();
                insertSuccess += newRoot.write(rootPid,pf);
                treeHeight++;
              }

              newKey = midKey;
              newPid = siblingPid;

              if (insertSuccess < 0)
                return -1;
              return 1;
            }
        node.write(pid, pf);
      } else if (insertSuccess == 0) {
        return 0;
      } else {
        return -1;
      }

    }
}
/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{   
  if (rootPid == -1){
    return -1;
  }
  int rc = locateRec(searchKey, cursor, 0, rootPid);
  return rc;
}

RC BTreeIndex::locateRec(int searchKey, IndexCursor& cursor, int depth, int pid)
{	int eid;
	PageId nextPid;

	if (depth == treeHeight) {
		BTLeafNode leaf = BTLeafNode();
		leaf.read(pid, pf);
		if (leaf.locate(searchKey,eid) < 0) {
			return -1;
		}
		cursor.pid = pid;
		cursor.eid = eid;
		return 0;

	} else {
		BTNonLeafNode nonleaf = BTNonLeafNode();
		nonleaf.read(pid, pf);
		if (nonleaf.locateChildPtr(searchKey, nextPid) < 0){
			return -1;
		}
		locateRec(searchKey,cursor,depth++,nextPid);
	}

}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    if (cursor.pid > pf.endPid() || cursor.pid < 1 || cursor.eid > (PageFile::PAGE_SIZE-4)/12) {
      return -1;
    }

    BTLeafNode leaf = BTLeafNode();
    leaf.read(cursor.pid,pf);
    int success = -1;

    success = leaf.readEntry(cursor.eid, key, rid);
    int keycount = leaf.getKeyCount();

    if (cursor.eid < keycount - 1) {
      cursor.eid++;
    } else {
      PageId nextPid = leaf.getNextNodePtr();
      if (nextPid == 0) { 
        return RC_INVALID_CURSOR;
      } else {
        cursor.pid = nextPid;
        cursor.eid = 0;
      }
    }
    return 0;
}

void BTreeIndex::printIndex() {
  if (treeHeight == 1) {
    BTLeafNode leaf = BTLeafNode();
    leaf.read(rootPid,pf);
    leaf.dumpNode();
  } else if (treeHeight > 0) {
    deque<PageId> nodes;
    BTNonLeafNode root = BTNonLeafNode();
    root.read(rootPid,pf);
    root.dumpNode();
    for (int i = 0; i < root.getKeyCount()+1; ++i) {
      nodes.push_back(root.pageIdAt(i));
    }
    nodes.push_back(-1);

    BTNonLeafNode node = BTNonLeafNode();
    BTLeafNode leaf = BTLeafNode();
    int depth = 2;
    while(nodes.size() != 0) {

      int curr = nodes[0];
      nodes.pop_front();

      if (curr == -1){
        depth++;
        cout << endl;
        if (depth <= treeHeight)
            nodes.push_back(-1);
      } else if (depth == treeHeight) {
        leaf.read(curr, pf);
        leaf.dumpNode();
        cout << "     ";
      } else {
        node.read(curr,pf);
        node.dumpNode();
        for (int i = 0; i < node.getKeyCount()+1; ++i) {
          nodes.push_back(node.pageIdAt(i));
        }
      }
    }
  }
}
